﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Corecalc;
using System.Diagnostics;

namespace Sisal
{
    public enum NodeState { NotReferenced, Referenced }

    public abstract class GRNode 
    {
        public static Dictionary<FullCellAddr, GRNode> nodeEnvironment = new Dictionary<FullCellAddr, GRNode>();
  
        public GRGraph Parent { get; set; }
        public Task Task { get; set; }
        public Task TempTask { get; set; }

        public double ExecutionTimeCost { get; set; }
        public List<GRNode> InputEdges { get; set; }   
        public List<GRNode> OutputEdges { get; set; }

        public bool DFSMarked { get; set; }

        public double Overhead { get; set; }
        public double CP { get; set; }

        public virtual double T_in { get; set; }
        public virtual double T_out { get; set; }

        public int F { get { return 1; } }      //Only set if IsFormulaNode is true
        public FullCellAddr Fca { get; set; }
        public bool IsFormulaNode { get; set; }
        public virtual NodeState State { get; set; }

        public int InpComCost {
            get { return InputEdges.Sum(e => e.OutComCost); }
        }

        public int OutComCost {
            get { return 0; }
        }

        public GRNode() {
            InputEdges = new List<GRNode>();
            OutputEdges = new List<GRNode>();
        }

        public abstract void SetCostsAndConnectWithFormulaNodes(FormulaNode node, FullCellAddr curr, Dictionary<FullCellAddr, GRNode> env, HashSet<FullCellAddr> path, Costs costs);

        //Returns the node in the graph represented by this node 
        //(should only be called on be the global root node)
        //Does not include sub graphs of compound- and parallel nodes

        //public virtual List<GRNode> GetGraph(bool subGraph) {
        //    List<GRNode> ns = new List<GRNode>();

        //    if (!ns.Contains(this)) {
        //        ns.Add(this);
        //    }

        //    List<GRNode> edges = subGraph ? InputEdges : OutputEdges;
        //    foreach (GRNode node in edges) {
        //        List<GRNode> nss = node.GetGraph(subGraph);
        //        foreach (GRNode node2 in nss) {
        //            if (!ns.Contains(node2)) {
        //                ns.Add(node2);
        //            }
        //        }
        //    }

        //    foreach (GRNode node in InputEdges) {
        //        if (node is UpToDateValueNode) {
        //            ns.Add(node);
        //        }
        //    }

        //    return ns;
        //}

        //Returns all nodes in the graph with this node as its root
        //Does NOT include subgraphs of compound and parallel nodes
        //public virtual List<GRNode> GetLocalGraph() {
        //    if (IsFormulaNode && Nodes != null) {
        //        return Nodes;
        //    } else if (IsFormulaNode && Nodes == null) {
        //        Nodes = GetLocalGraphNodes();
        //        return Nodes;
        //    } else {
        //        return GetLocalGraphNodes();
        //    }
        //}

        //private List<GRNode> GetLocalGraphNodes() {
        //    List<GRNode> ns = new List<GRNode>();
        //    foreach (GRNode inp in InputEdges) {
        //        if (!inp.IsFormulaNode && inp.FormulaNode == this.FormulaNode) {
        //            ns.AddRange(inp.GetLocalGraphNodes());
        //        }
        //    }

        //    ns.Add(this);
        //    return ns;
        //}

        //public virtual void SetParent(GRNode parent, GRNode complexAncestor, bool @continue, List<FullCellAddr> path) {
        //    Parent = parent;
        //    ComplexAncestor = complexAncestor;

        //    //If the sender of a value (inputedge) is not on the path from the root to this node (via output edges), 
        //    //then we need to set its parent recursively using the input edges of this node
        //    foreach (GRNode inputEdge in InputEdges) {
        //        if (!path.Contains(inputEdge.Fca) || Fca == inputEdge.Fca) {
        //            inputEdge.SetParent(parent, complexAncestor, false, path);
        //        }
        //    }

        //    if (@continue) {
        //        foreach (GRNode node in OutputEdges)
        //            node.SetParent(parent, complexAncestor, true, path);
        //    }
        //}

        //public void SetFormulaNode(GRNode formulaNode) {
        //    FormulaNode = formulaNode;

        //    foreach (GRNode node in InputEdges)
        //        node.SetFormulaNode((node.IsFormulaNode ? node : formulaNode));
        //}

        public void DFS(Action<GRNode> f) {
            HashSet<GRNode> nodes = new HashSet<GRNode>();

            Stack<GRNode> stack = new Stack<GRNode>();
            stack.Push(this);
            while (stack.Count() > 0) {
                GRNode node = stack.Pop();
                if (!node.DFSMarked) {
                    f(node);
                    node.DFSMarked = true;
                    nodes.Add(node);
                    foreach (GRNode outputEdge in node.OutputEdges) {
                        stack.Push(outputEdge);
                    }
                }
            }

            foreach (GRNode node in nodes) {
                node.DFSMarked = false;
            }
        }

        public virtual bool IsConstNode { get { return false; } }

        public override string ToString() {
            return string.Format("[Loc: {0}, Formula: {1}, Tin: {2}, Tout: {3}]: \t", 
                Fca.ca,
                IsFormulaNode, 
                T_in, 
                T_out);
        }
    }

    abstract class SimpleNode : GRNode
    {

    }

    abstract class CompoundNode : GRNode
    {

    }

    // Represents genuine calls to built-in functions. 
    // Calls like "SUM(A1:B2)", "AVG(A1:B)" etc.
    class BuiltInFunctionCallNode : GRNode
    {
        public string Name { get; set; }
        public GRNode[] Args { get; set; }
        public int LastInputSize { get; set; }
        public bool Par { get; set; }

        public BuiltInFunctionCallNode(string name, GRNode[] args, double t_out) {
            Name = name;
            Args = args;
            LastInputSize = 0;

            foreach (GRNode arg in args) {
                InputEdges.Add(arg);
                arg.OutputEdges.Add(this);
            }

            Debug.Assert(name.Equals("SUM") || name.Equals("COS") || name.Equals("SIN") || name.Equals("SQRT"));

            T_in = args.Sum(arg => arg.T_out);
            T_out = t_out;
        }

        public override void SetCostsAndConnectWithFormulaNodes(FormulaNode node, FullCellAddr curr, Dictionary<FullCellAddr, GRNode> env, HashSet<FullCellAddr> path, Costs costs) {
            foreach (GRNode arg in Args) {
                arg.SetCostsAndConnectWithFormulaNodes(node, curr, env, path, costs);
            }
            
            Func<GRNode[], double> timeEstimator = Function.TimeEstimatorFor(Name);
            costs.Ft += timeEstimator(InputEdges.ToArray());
        }

        public override string ToString() {
            return base.ToString() + string.Format("BuiltInFunctionCallNode [name: {0}]", Name);
        }
    }

    abstract class ParallelNode : GRNode
    {
        public double F { get; set; }
        public int Size { get; set; }
        public GRNode Graph { get; set; }

        public ParallelNode(GRNode g) {
            Graph = g;
            F = 1.0;
        }
    }

    class CellRefNode : SimpleNode
    {
        public FullCellAddr ReferredFca { get; set; }

        public CellRefNode(FullCellAddr referredFca) {
            ReferredFca = referredFca;
        }

        public override void SetCostsAndConnectWithFormulaNodes(FormulaNode node, FullCellAddr curr, Dictionary<FullCellAddr, GRNode> env, HashSet<FullCellAddr> path, Costs costs) {
            Sheet sheet = ReferredFca.sheet;
            CellAddr ca = ReferredFca.ca;

            GRNode referredNode = null;
            if(env.ContainsKey(ReferredFca)) {
                referredNode = env[ReferredFca];
                costs.T_in += referredNode.T_out;
            } else if (path.Contains(ReferredFca)) {
                referredNode = sheet[ca].Expand(ReferredFca, env, path);            //Expand on a cell calls SetCostsAndConnectWithFormulaNodes, so no need to call it explicitly
                costs.T_in += referredNode.T_out;
            } else {
                referredNode = new ConstNode(ReferredFca, curr);
                referredNode.SetCostsAndConnectWithFormulaNodes(node, curr, env, path, costs);
            }

            T_in = T_out = referredNode.T_out;

            node.InputEdges.Add(referredNode);
            referredNode.OutputEdges.Add(node);
        }

        public override string ToString() {
            return base.ToString() + string.Format("CellRefNode [InputEdges: {0}]", InputEdges.Count());
        }
    }
    
    class CellAreaNode : SimpleNode
    {
        public CellArea Area { get; set; }

        public CellAreaNode(CellArea area) {
            Area = area;
        }

        public override void SetCostsAndConnectWithFormulaNodes(FormulaNode node, FullCellAddr curr, Dictionary<FullCellAddr, GRNode> env, HashSet<FullCellAddr> path, Costs costs) {
            Sheet sheet = curr.sheet;
            CellAddr upperLeft = Area.ul.Addr(curr.ca.col, curr.ca.row);
            CellAddr lowerRight = Area.lr.Addr(curr.ca.col, curr.ca.row);

            Area.ForEachReferred(sheet, curr.ca.col, curr.ca.row, referredFca => {
                if (path.Contains(referredFca)) {
                    Cell cell = sheet[referredFca.ca];

                    GRNode referredNode = null;
                    if (env.ContainsKey(referredFca)) {
                        referredNode = env[referredFca];
                    } else {
                        referredNode = sheet[referredFca.ca].Expand(referredFca, env, path);
                    }

                    //If a formula refers contains a CellRef twice, then only record I/O-edges and cost the first time
                    if (!node.InputEdges.Contains(referredNode)) {
                        node.InputEdges.Add(referredNode);
                        referredNode.OutputEdges.Add(node);

                        T_in += referredNode.T_out;             //Add T_out to CellAreaNode's T_in
                        T_out += referredNode.T_out;            //Add T_out to CellAreaNode's T_out for execution time cost assignment by timeEstimator function
                        costs.T_in += referredNode.T_out;       //Add T_out to T_in of formula node
                    }
                } else {
                    ConstNode cn = new ConstNode(referredFca, curr);
                    node.InputEdges.Add(cn);
                    cn.OutputEdges.Add(node);
                    cn.SetCostsAndConnectWithFormulaNodes(node, curr, env, path, costs);
                    T_in += cn.T_out;                           //Add T_out to CellAreaNode's T_in
                    T_out += cn.T_out;                          //Add T_out to CellAreaNode's T_out for execution time cost assignment by timeEstimator function
                }
            });
        }

        public override string ToString() {
            return base.ToString() + string.Format("CellAreaNode [InputEdges: {0}]", InputEdges.Count());
        }
    }

    class BinOperator : SimpleNode
    {
        public string Operator  { get; set; }
        public GRNode Left { get; set; }
        public GRNode Right { get; set; }

        public BinOperator(string binOp, GRNode left, GRNode right, double t_out) {
            Operator = binOp;
            Left = left;
            Right = right;
            T_out = t_out;

            this.InputEdges.Add(left);
            this.InputEdges.Add(right);

            left.OutputEdges.Add(this);
            right.OutputEdges.Add(this);
        }

        public override void SetCostsAndConnectWithFormulaNodes(FormulaNode node, FullCellAddr curr, Dictionary<FullCellAddr, GRNode> env, HashSet<FullCellAddr> path, Costs costs) {
            Left.SetCostsAndConnectWithFormulaNodes(node, curr, env, path, costs);
            Right.SetCostsAndConnectWithFormulaNodes(node, curr, env, path, costs);

            costs.Ft += MultiProcessorModel.GetExecutionTime(Operator);
        }

        public override string ToString() {
            return base.ToString() + string.Format("BinOperator [{0}]", Operator);
        }
    }

    class IfNode : CompoundNode
    {
        public GRNode Cond { get; set; }
        public GRNode TrueBranch { get; set; }
        public GRNode FalseBranch { get; set; }

        public IfNode(GRNode cond, GRNode trueBranch, GRNode falseBranch) {
            Cond = cond;
            TrueBranch = trueBranch;
            FalseBranch = falseBranch;

            T_in = cond.T_out;
            T_out = Math.Max(trueBranch.T_out, falseBranch.T_out);
        }

        public override void SetCostsAndConnectWithFormulaNodes(FormulaNode node, FullCellAddr curr, Dictionary<FullCellAddr, GRNode> env, HashSet<FullCellAddr> path, Costs costs) {
            Costs trueCosts = new Costs();
            Costs falseCosts = new Costs();

            Cond.SetCostsAndConnectWithFormulaNodes(node, curr, env, path, costs);
            TrueBranch.SetCostsAndConnectWithFormulaNodes(node, curr, env, path, trueCosts);
            FalseBranch.SetCostsAndConnectWithFormulaNodes(node, curr, env, path, falseCosts);

            costs.T_in += Math.Max(trueCosts.T_in, falseCosts.T_in);
            costs.Ft += Math.Max(trueCosts.Ft, falseCosts.Ft);
        }

        public override string ToString() {
            return base.ToString() + string.Format("IfNode: [InputEdges: {0}, OutputEdges: {1}]", InputEdges.Count, OutputEdges.Count);
        }
    }

    class ConstNode : SimpleNode
    {
        public Const Const { get; set; }
        public FullCellAddr UptodateFca { get; set; }       //Non-null if represents a cell not on the path
        public bool RepresentsUptodateValue { get; set; }

        public ConstNode(Const value, FullCellAddr fca) {
            Const = value;
            Fca = fca;
            T_out = Const == null ? MultiProcessorModel.GetCommunicationCost(UptodateFca) : Const.CommunicationCost(UptodateFca);
            RepresentsUptodateValue = false;
        }

        //The result of expanding a cell ref that
        //represents a cell with state Uptodate
        public ConstNode(FullCellAddr fca, FullCellAddr hostFca) {
            UptodateFca = fca;  //The address of the cell which is Uptodate
            Fca = hostFca;      //The address of the cell that hosts the cellref which was expanded into this Const
            T_out = Const == null ? MultiProcessorModel.GetCommunicationCost(UptodateFca) : Const.CommunicationCost(UptodateFca);
            RepresentsUptodateValue = true;
        }

        public override void SetCostsAndConnectWithFormulaNodes(FormulaNode node, FullCellAddr curr, Dictionary<FullCellAddr, GRNode> env, HashSet<FullCellAddr> path, Costs costs) {
            costs.Ft += MultiProcessorModel.GetExecutionTime("Const");

            if (RepresentsUptodateValue)
                costs.T_in += T_out;
        }

        public override string ToString() {
            return base.ToString() + string.Format("ConstNode [value: {0}]", Const.ToString());
        }

        public override bool IsConstNode {
            get { return true; }
        }
    }


    public class FormulaNode : GRNode
    {
        public GRNode ExprRoot { get; set; }

        public FormulaNode(GRNode root) {
            ExprRoot = root;
        }

        public override void SetCostsAndConnectWithFormulaNodes(FormulaNode node, FullCellAddr curr, Dictionary<FullCellAddr, GRNode> env, HashSet<FullCellAddr> path, Costs costs) {
            throw new System.NotImplementedException();
        }

        public override string ToString() {
            return string.Format("FormulaNode [Fca: {0}, T_in: {1}, T_out: {2}, Ft: {3}]", Fca, T_in, T_out, ExecutionTimeCost);
        }
    }
}
